Labeled Transition System

释义 Definition

标记迁移系统（常写作 LTS）：一种形式化模型，用来描述系统如何从一个状态通过带有标签（通常表示动作、事件或输入）的迁移到达另一个状态。常用于并发系统、协议描述、过程代数与模型检测中。

发音 Pronunciation

/ˈleɪbəld trænˈzɪʃən ˈsɪstəm/

例句 Examples

A labeled transition system can represent the behavior of a simple vending machine.
标记迁移系统可以表示一个简单自动售货机的行为。

Using a labeled transition system, we model the protocol as states and action-labeled transitions, then verify safety properties.
我们用标记迁移系统把协议建模为一组状态和带动作标签的迁移，并据此验证安全性性质。

词源 Etymology

该术语由三部分构成：labeled（“带标签的”）+ transition（“状态迁移/转移”）+ system（“系统”）。在计算机科学的自动机理论与并发理论发展中，为了清晰表达“系统在执行某个动作后会到达哪个状态”，逐渐形成了用“带标签的边”连接“状态结点”的表述方式，并在过程代数（如 CCS）与模型检测领域被广泛采用。

相关词 Related Words

• Automaton
• State
• Transition
• Label
• Kripke Structure
• Finite-State Machine
• Bisimulation
• Model Checking
• Process Algebra
• Transition System

文学与著作中的用例 Literary Works

• Communication and Concurrency（Robin Milner）：并发理论与过程演算语境中常用 LTS 描述系统行为。
• Principles of Model Checking（Baier & Katoen）：用 LTS/迁移系统作为模型检测的核心建模对象之一。
• Model Checking（Clarke, Grumberg & Peled）：在形式化验证中以迁移系统表述被验证系统的状态空间。
• Concurrency: State Models and Java Programs（Magee & Kramer）：用状态模型（包括 LTS 风格表示）讲解并发系统的行为建模。